#pragma once

#define _CRT_SECURE_NO_WARNINGS 1

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>

typedef char BTDataType;

typedef struct BTree
{
	BTDataType val;
	struct BTree* left;
	struct BTree* right;
}BTree, *PBTree;

PBTree BuyNewNode();

///////////////////////////////////////////////////////////////////////////

typedef char SDataType;

typedef struct StackNode
{
	SDataType val;
	struct StackNode* next;
}StackNode, * PStackNode;

typedef struct Stack
{
	PStackNode top;
}Stack, * PStack;

///////////////////////////////////////////////////////////////////////////

typedef PBTree SDataType2;

typedef struct StackNode2
{
	SDataType2 val;
	struct StackNode2* next;
}StackNode2, * PStackNode2;

typedef struct Stack2
{
	PStackNode2 top;
}Stack2, * PStack2;

///////////////////////////////////////////////////////////////////////////

bool StackEmpty(PStack S);
int StackSize(PStack S);
void StackPrint(PStack S);
PStack StackCreate();
void StackDestroy(PStack* pS);
void StackPush(PStack S, SDataType x);
void StackPop(PStack S);
SDataType StackTop(PStack S);

///////////////////////////////////////////////////////////////////////////

bool StackEmpty(PStack2 S);
int StackSize(PStack2 S);
PStack2 StackCreate2();
void StackDestroy(PStack2* pS);
void StackPush(PStack2 S, SDataType2 x);
void StackPop(PStack2 S);
SDataType2 StackTop(PStack2 S);

///////////////////////////////////////////////////////////////////////////

